
package trim.testalgorithms;

import java.util.*;

import trim.common.*;
import trim.common.inputdata.*;
import trim.common.result.*;
import trim.common.bp.*;

import trim.differentmaterials.core.*;
import trim.differentmaterials.generator.core.*;
import trim.differentmaterials.coefficients.*;
import trim.differentmaterials.generator.columns.*;

/**
 *
 * @author Podorov Alexander
 */

public class BBRestTrimmer extends RestTrimmer
{
    private Coefficients coefficients;

    public BBRestTrimmer(TrimCore core, Generator generator, Coefficients coefficients)
    {
        super(core, generator);

        this.coefficients = coefficients;
    }

    private class FormatCountIndex
    {
        private Format format;
        private int count;
        private int index;

        public FormatCountIndex(Format format, int count, int index)
        {
            this.format = format;
            this.count = count;
            this.index = index;
        }

        public Format getFormat()
        {
            return format;
        }

        public int getCount()
        {
            return count;
        }

        public int getIndex()
        {
            return index;
        }

        public void decreaseCount()
        {
            count--;
        }
    }

    private class Heap
    {
        private Material material;
        private List<FormatCountIndex> items;
        private int rest;
        //private int minRest;

        public Heap(Material material)
        {
            this.material = material;
            items = new ArrayList<FormatCountIndex>();
            rest = material.getLength();
            //minRest = rest;
        }

        public Material getMaterial()
        {
            return material;
        }

        public List<FormatCountIndex> getItems()
        {
            return items;
        }

        public int getRest()
        {            
            return rest;
        }

        /*public boolean isOptimal()
        {
            return minRest >= rest;
        }*/

        public int getSize()
        {
            return items.size();
        }

        public void put(Format format, int count, int index)
        {
            rest -= format.getLength() * count;
            items.add(new FormatCountIndex(format, count, index));
            //minRest = rest;
        }

        public int popIndex()
        {
            FormatCountIndex item = items.get(items.size() - 1);
            if (item.getCount() == 1)
            {
                items.remove(items.size() - 1);
            }
            else
            {
                item.decreaseCount();
            }
            rest += item.getFormat().getLength();
            return item.getIndex();
        }

        public void clearHeap(FormatOrder[] formatOrderRest)
        {
            for (FormatCountIndex item : items)
            {
                formatOrderRest[item.getIndex()].setCount(formatOrderRest[item.getIndex()].getCount() + item.getCount());
            }
            items.clear();
            rest = material.getLength();
            //minRest = rest;
        }
    }

    private List<Heap> lowerBound(MaterialStock[] materials, int length, boolean useRestrictions)
    {
        int tail = length;
        int count = 0;
        int value = 0;
        int record = 0;
        int dimension = materials.length;
        int[] items = new int[dimension];
        int[] bestItems = new int[dimension];
        int current = 0;
        int lastFormat = 0;
        int[] list = new int[dimension];
        int last = - 1;
        boolean exit = false;

        do
        {
            for (int i = current; i < dimension; i++)
            {
                if (useRestrictions)
                {
                    items[i] = Math.min(tail / materials[i].getMaterial().getLength(), Math.abs(materials[i].getCount()));
                }
                else
                {
                    items[i] = tail / materials[i].getMaterial().getLength();
                }
                if (items[i] > 0)
                {
                    tail -= items[i] * materials[i].getMaterial().getLength();
                    value = length - tail;
                    count += items[i];
                    list[++last] = i;
                }
            }
            if (record < value)
            {
                record = value;
                for (int i = 0; i < dimension; i++)
                {
                    bestItems[i] = items[i];
                }
            }
            if (record == length)
            {
                exit = true;
            }
            else
            {
                if (last >= 0)
                {
                    lastFormat = list[last];
                    if (items[lastFormat] == 1)
                    {
                        last--;
                    }
                    items[lastFormat]--;
                    tail += /*items[lastFormat] * */ materials[lastFormat].getMaterial().getLength(); ///!!!!!!!!!!!!!!!!
                    value = length - tail;
                    count--;
                    current = lastFormat + 1;
                }
                else
                {
                    exit = true;
                }
            }
        }
        while (!exit);

        if (record < length)
        {
            bestItems[dimension - 1]++;
        }        

        /*int heapDimension = 0;
        for (int i = 0; i < dimension; i++)
        {
            heapDimension += bestItems[i];
        }*/

        List<Heap> heaps = new ArrayList<Heap>();
        //int nextHeap = 0;
        for (int i = 0; i < dimension; i++)
        {
            for (int j = 0; j < bestItems[i]; j++)
            {
                //heaps[nextHeap++] = new Heap(materials[i].getMaterial());
                heaps.add(new Heap(materials[i].getMaterial()));
            }
        }

        return heaps;
    }

    private int lengthToNumber(int length)
    {
        for (int i = 0; i < formatCount; i++)
        {
            if (formatOrder[i].getFormat().getLength() == length)
            {
                return i;
            }
        }
        return - 1;
    }

    private void process()
    {
        int totalFormatLength = 0;        

        FormatOrder[] formatOrderRest = new FormatOrder[formatCount];
        for (int i = 0; i < formatCount; i++)
        {
            formatOrderRest[i] = new FormatOrder(formatOrder[i].getFormat(), formatRests[i]);
            totalFormatLength += formatOrder[i].getFormat().getLength() * formatRests[i];
        }
        Arrays.sort(formatOrderRest, new Comparator<FormatOrder>() {
            public int compare(FormatOrder formatOrder1, FormatOrder formatOrder2)
            {
                return formatOrder2.getFormat().getLength() - formatOrder1.getFormat().getLength();
            }
        });

        MaterialStock[] materialStockRest = new MaterialStock[materialCount];
        for (int i = 0; i < materialCount; i++)
        {
            materialStockRest[i] = new MaterialStock(materialStock[i].getMaterial(), materialRests[i]);
        }
        Arrays.sort(materialStockRest, new Comparator<MaterialStock>() {
            public int compare(MaterialStock materialStock1, MaterialStock materialStock2)
            {
                return materialStock2.getMaterial().getLength() - materialStock1.getMaterial().getLength();
            }
        });

        List<Heap> heaps = lowerBound(materialStockRest, totalFormatLength, false);

        int currentHeap = 0;
        //int heapDimension = heaps.length;

        int maxRest = 0;
        int tempRest = 0;

        for (int i = 0; i < heaps.size(); i++)
        {
            maxRest += heaps.get(i).getMaterial().getLength();
        }
        maxRest -= totalFormatLength;

        ////////////////////////////////////////////

        int sum1 = 0;
        for (int i = 0; i < formatCount; i++)
        {
            sum1 += formatOrderRest[i].getCount();
        }





        int iter =0;

        /*int sum2 = 0;
            for (int i =0; i <formatCount;i++)
            {
                sum2+=formatOrderRest[i].getCount();
            }
            for (int i=0;i<heaps.size();i++)
            {
                Heap h = heaps.get(i);
                for (int j=0; j <h.getItems().size(); j++)
                {
                    sum2+= h.getItems().get(j).getCount();
                }
            }

            if (sum1 != sum2)
            {
                System.out.println("s1 <> s2!");
            }*/

        //////////////////////////////////////////////

        //int h = 0;

        ////////////////////////////////////


        /*InputData in = new InputData();

        for (int i = 0; i < formatCount; i++)
        {
            if (formatOrderRest[i].getCount() > 0)
            {
                in.getFormatOrderList().add(formatOrderRest[i]);
            }
        }
        MaterialStock ms = new MaterialStock(materialStockRest[0].getMaterial(), 10000);
        in.getMaterialStockList().add(ms);

        try
        {
             TrimResult tr = new BestPartition(in).solve(5);

             int r=0;

             for (int i = 0; i < tr.size(); i++)
             {
                 System.out.println(tr.get(i).getPatternTail());
             }
        }
        catch (Exception e)
        {
            e.printStackTrace();
        }*/
      





        ////////////////////////////////////        


        /*while (currentHeap < heaps.size())
        {
            boolean exit = false;
            int currentFormat = 0;

            while (!exit)
            {
                for (int i = currentFormat; i < formatCount; i++)
                {
                    int count = Math.min(heaps.get(currentHeap).getRest() / formatOrderRest[i].getFormat().getLength(), formatOrderRest[i].getCount());
                    if (count > 0)
                    {
                        heaps.get(currentHeap).put(formatOrderRest[i].getFormat(), count, i);
                        formatOrderRest[i].setCount(formatOrderRest[i].getCount() - count);
                    }
                }
                
                //tempRest += heaps.get(currentHeap).getRest();

                if (tempRest + heaps.get(currentHeap).getRest() > maxRest)                
                {                   

                    if (heaps.get(currentHeap).getSize() <= 0)
                    {
                        //int h=0;
                        
                        for (int i = currentHeap - 1; i > 0; i--)
                        {
                            tempRest -= heaps.get(i).getRest();
                            heaps.get(i).clearHeap(formatOrderRest);
                        }

                        

                        currentHeap = 0;
                        tempRest = 0;
                    }

                    //if (heaps.get(currentHeap).getSize() <= 0)
                    //{
                    //    heaps.add(new Heap(materialStockRest[materialCount - 1].getMaterial()));
                    //    currentFormat = 0;
                    //    maxRest += materialStockRest[materialCount - 1].getMaterial().getLength();
                    //    tempRest = 0;
                    //}

                    //else
                    //{
                        int last = heaps.get(currentHeap).popNumber();

                        
                        
                        formatOrderRest[last].setCount(formatOrderRest[last].getCount() + 1);
                        currentFormat = last + 1;
                    //}
                }
                else
                {
                    exit = true;                    
                }
            }

            tempRest += heaps.get(currentHeap).getRest();
            currentHeap++;
        }*/




        int back = 0;

        int last = - 1;
        int currentFormat = 0;

        while (currentHeap < heaps.size())
        {            

            for (int i = currentFormat; i < formatCount; i++)
            {
                int count = Math.min(heaps.get(currentHeap).getRest() / formatOrderRest[i].getFormat().getLength(), formatOrderRest[i].getCount());
                if (count > 0)
                {
                    heaps.get(currentHeap).put(formatOrderRest[i].getFormat(), count, i);
                    formatOrderRest[i].setCount(formatOrderRest[i].getCount() - count);                    
                }
            }            

            if (heaps.get(currentHeap).getSize() > 0)
            {
                if ((tempRest + heaps.get(currentHeap).getRest() <= maxRest) )
                {
                    tempRest += heaps.get(currentHeap).getRest();
                    currentHeap++;
                    currentFormat = 0;

                    /*if (currentHeap >= heaps.size() - 1)
                    {
                        System.out.print(iter++ + ") " + currentHeap + " [");

                        for (int k=0; k<heaps.size(); k++)
                        {
                            System.out.print(heaps.get(k).getRest() + ",");
                        }
                        System.out.println("] ");
                    }*/

                    
                }
                else
                {
                    last = heaps.get(currentHeap).popIndex();
                    formatOrderRest[last].setCount(formatOrderRest[last].getCount() + 1);
                    currentFormat = last + 1;
                }
            }
            else
            {
                /*for (int i = currentHeap - 1; i > back; i--)
                {
                    tempRest -= heaps.get(i).getRest();
                    heaps.get(i).clearHeap(formatOrderRest);
                }

                currentHeap = back;

                if (heaps.get(currentHeap).getSize() > 0)
                {
                    tempRest -= heaps.get(currentHeap).getRest();

                    last = heaps.get(currentHeap).popIndex();
                    formatOrderRest[last].setCount(formatOrderRest[last].getCount() + 1);
                    currentFormat = last + 1;
                }
                else
                {
                    System.out.println("err");
                    //currentHeap = 0;
                    //currentFormat = 0;
                    //back++;
                    //heaps.add(new Heap(new Material(6370)));
                }*/




                //if (heaps.get(currentHeap).getSize() > 0)
                //{
                    if (currentHeap == 0)
                    {
                        heaps.add(new Heap(new Material(materialStockRest[materialCount - 1].getMaterial())));
                        currentHeap = 0;
                        currentFormat = 0;
                        maxRest += heaps.get(heaps.size() - 1).getMaterial().getLength();
                    }
                    else
                    {
                        currentHeap--;
                        tempRest -= heaps.get(currentHeap).getRest();
                        last = heaps.get(currentHeap).popIndex();
                        formatOrderRest[last].setCount(formatOrderRest[last].getCount() + 1);
                        currentFormat = last + 1;
                    }

                    
                    
                //}
                //else
                //{
                    //System.out.println("error");
                    //heaps.add(new Heap(new Material(materialStockRest[materialCount - 1].getMaterial())));
                    //currentHeap = 0;
                    //currentFormat = 0;
                    //maxRest += heaps.get(heaps.size() - 1).getMaterial().getLength();
                //}
            }
        }

        
        
        




        for (int i = 0; i < heaps.size(); i++)
        {
            int[] items = new int[formatCount];
            for (FormatCountIndex item : heaps.get(i).getItems())
            {
                items[lengthToNumber(item.getFormat().getLength())] = item.getCount();
            }
            RealPattern pattern = new RealPattern(items, Double.MAX_VALUE, coefficients.getCoefficient(RealPattern.class), heaps.get(i).getMaterial());
            pattern.setCount(1);
            patterns.add(pattern);
        }
    }

    public void start() throws NoSolutionsException
    {        
        setFormatRests();
        setMaterialRests();

        process();
    }
}
